The present invention relates to integrated circuits and, more particularly, to logic simulation of integrated circuits. A major objective of the present invention is to provide for more efficient event-driven logic simulation of very large scale integrated circuits.
Much of modern technological progress is identified with miniaturization of integrated circuits. Miniaturization allows for increased functionality by increasing the number of logic elements circuits that can be integrated onto a single integrated circuit device. Recently, semiconductor processing has permitted an evolution from large scale integration (LSI) to very large scale integration (VLSI) circuits. The increased integration has provided for improved performance.
However, to provide this increased integration and performance economically, it is necessary to avoid manufacturing defectively designed circuits. This avoidance is accomplished by simulating the performance of a circuit design through what is called "logic simulation". Logic simulation involves construction of a model of an integrated circuit, and the evaluation of the response of the model to simulated input events.
There are two basic approaches to logic simulation: levelized logic simulation and event-driven logic simulation. Both approaches construct a circuit model which specifies components of the circuit and the signals that define the relations among these components and between the circuit and an incorporating system. Both approaches specify changes in selected signals to determine the effects of those changes on other signals. The effects are defined by functions associated with respective components having the selected signals as inputs and the affected signals as outputs.
In levelized logic simulations, the effect of a specified signal change is evaluated for the entire circuit. Once this evaluation is complete, a second signal change can be introduced for evaluation. Levelized logic simulation requires that the circuit model order the components so that components receiving a signal as inputs are evaluated after the component generating the signal as an output.
There are three basic limitations of levelized logic simulations. First, the circuit must be analyzed to order the components. Second, because components must be ordered, circuits with feedback loops require special evaluation techniques. Third, levelized logic simulations tend to require superfluous evaluations of components whose inputs have not changed. Various strategies have been employed, with varying degrees of effectiveness, to avoid time-consuming evaluations of components that cannot be affected by a given signal change. However, these have met with only limited success.
Event-driven logic simulation addresses all three of these disadvantages. First, components and signals need not be ordered. Second and therefore, feedback loops can be handled routinely. Third, only components with changed inputs are evaluated.
One of the tradeoffs is that event-driven logic simulations can generate a large number of "uninteresting" events which are evaluated as a matter of course. These superfluous evaluations waste valuable computer time. The present invention is directed to minimizing these superfluous evaluations so as to reduce the time and complexity of event-driven logic simulations.
In a typical event-driven simulation, the circuit model is represented by a signal list and a component list, the latter being conveniently separated into a component instance list and a component type list. The signal list is a database in which the records (usually, rows when the list is represented as a table) correspond to respective circuit signals. Typically, the fields (column heading) include the signal name, the source of the signal, the signal destinations, the current status of the signal, and the time at which the current status was most recently attained.
The component instance list is a database in which the records correspond to components. Typically, the following fields are included in the component instance list: component name, component type, the signals received at its inputs, and the signals generated at its outputs. The component type entry is used to address the component type list, which describes the function performed by the component. The component function can specify timing relationships as well as the logical relationship between inputs and outputs. The timing relationship can specify how long it will take an input change to be reflected at an output. For example, a function for an inverter can specify that a change in the input to an inverter will cause the inverter output to undergo the opposing change two nanoseconds (ns) later. This timing relationship can be specified for each input-output pair.
The inputs to the circuit characterized by the signal and component lists can be specified in an event queue. This queue specifies a chronological series of events, including signal status events. A signal status event specifies a signal to be changed, a value or status to which the specified signal is to be changed, and a simulation time at which the specified change is to occur.
A queue manager can select the earliest event, i.e., the one with the earliest specified time, for processing. The signal name specified by the selected signal event is used to address the signal list. The specified new signal status, e.g., a logic high (1), a logic low (0), a high-impedance state (Z), or possibly an uncertain status (U), is recorded in the status field for the appropriate record. In addition, the present simulation time is recorded in the "most-recent-transition" (MRT) time entry in the signal's record. The signal list also specifies the component(s) which serves (serve) as the signal's destination; a signal can have more than one destination.
The destination specified in the specified signal's record is used to select the destination component's record in the component instance list. The component instance list specifies which input receives the changed signal. It also specifies which signals are received by other inputs of the component. The component instance list also specifies the type of the destination component.
The component type information is used to address the component type list which specifies the function for the component. This function is scheduled for evaluation at the present simulation time, unless a flag is set indicating that no evaluation is to follow a change at the destination input. For example, changes in data inputs to flip-flops do not require evaluation since the data inputs do not affect flip-flop outputs except when a clock signal enables the flip-flop. Therefore, evaluation of the flip-flop occurs when a signal status event specifies the required signal change in the clock input to the flip-flop.
The evaluation is scheduled for the present time, rather than executed immediately. Other presently scheduled signal status events are processed before any presently scheduled evaluation events. This strategy is designed to handle cases where two inputs of a component change at the same time. Evaluating between simultaneous input changes generally results in misleading output evaluations. Postponing the evaluation insures that all "recent" signal data is available for the evaluation. In addition, this strategy allows one of the scheduled evaluations to be dropped, minimizing the time required for evaluation.
Despite such strategies such as scheduling present evaluations after present signal status events, event-driven logic simulations can readily generate superfluous events and evaluations. "Uninteresting" transition artifacts can be generated when two inputs of a component change at slightly different times. For example, in the worst case input changes could be received at thirty-two slightly different times by a 16+16-bit multiplier. A simulator would have to perform 32 complex evaluations, only the last of which is really of interest. Each of the other 31 evaluations would generate up to 32 new statuses at the output of the multiplier (assuming it had 32 outputs). Each of these 32 outputs could affect one or more other components, depending on fanouts from the multiplier. Each component receiving a multiplier output could require further evaluations.
Component evaluation is computationally intensive. Minimizing superfluous evaluations and the chain reaction they can cause would greatly increase the efficiency of event-driven simulations. This would reduce the time and cost required for circuit simulation, in turn, making circuit design more cost effective.